package com.heima.leetcode.practice;

import java.util.List;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 120. 三角形最小路径和
 * @date 2025/5/23 10:35
 */
public class E120 {

    /**
     * 最小路径和
     */
    private int min = Integer.MAX_VALUE;

    /**
     * 方法一：多路递归，不能全部通过
     *
     * @param triangle 三角形
     * @return 最小路径和
     */
    public int minimumTotal1(List<List<Integer>> triangle) {
        recursive(triangle, 0, 0, 0);
        return min;
    }

    /**
     * 递归
     *
     * @param triangle 三角形
     * @param index    索引
     * @param length   长度
     * @param sum      当前和
     */
    private void recursive(List<List<Integer>> triangle, int index, int length, int sum) {
        if (length == triangle.size()) {
            min = Math.min(min, sum);
            return;
        }
        int num = triangle.get(length).get(index);
        recursive(triangle, index, length + 1, sum + num);
        recursive(triangle, index + 1, length + 1, sum + num);
    }

    /**
     * 方法二：动态规划，自顶向下
     *
     * @param triangle 三角形
     * @return 最小路径和
     */
    public int minimumTotal2(List<List<Integer>> triangle) {
        int[] dp = new int[triangle.size()]; // 高度和最后一行的元素个数相同
        dp[0] = triangle.get(0).get(0);
        for (int i = 1; i < dp.length; i++) {
            // 这里要从右向左，不然会覆盖上一行的dp[j - 1]
            for (int j = i; j >= 0; j--) {
                if (j == 0) {
                    dp[j] = dp[j] + triangle.get(i).get(j);
                } else if (j == i) {
                    dp[j] = dp[j - 1] + triangle.get(i).get(j);
                } else {
                    dp[j] = triangle.get(i).get(j) + Math.min(dp[j - 1], dp[j]);
                }
            }
        }
        int min = dp[0];
        for (int i = 1; i < dp.length; i++)
            if (dp[i] < min) min = dp[i];
        return min;
    }

    /**
     * 方法三：动态规划，自底向上
     *
     * @param triangle 三角形
     * @return 最小路径和
     */
    public int minimumTotal3(List<List<Integer>> triangle) {
        int[] dp = new int[triangle.size()];
        for (int i = 0; i < dp.length; i++)
            dp[i] = triangle.get(dp.length - 1).get(i);
        for (int i = dp.length - 2; i >= 0; i--)
            for (int j = 0; j <= i; j++)
                dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j + 1]);
        return dp[0];
    }
}
